package Sort_06;

/*
 * @Author 罗
 * @date 2020/3/18 - 12:31 下午
 * 归并排序
 * 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略
 * （分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)
 */

import org.junit.Test;

import java.util.Arrays;

public class MergeSorting_07 {

    @Test
    public void test() {
        int[] array = {8, 4, 5, 7, 1, 3, 6, 2};
        /*
         * 归并排序所需要的额外空间
         * */
        int[] temp = new int[array.length];
        mergeSorting(array, 0, array.length - 1, temp);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 时间复杂度 O(n log2n) 线性
     * 稳定
     *
     * @param array 需要排序的数组
     * @param left  array中需要排序的左边界
     * @param right array中需要排序的右边界
     * @param temp  用于临时存放排序结果的数组
     */
    public static void mergeSorting(int[] array, int left, int right, int[] temp) {
        /*
         * 递归的时候，分组还没有被分解为每组只有2个元素，就继续进行分组
         * */
        if (left < right) {
            int mid = (left + right) / 2;
            /*
             * 拆分
             * 1.向左进行递归分解
             * */
            mergeSorting(array, left, mid, temp);
            /*
             * 2.向右进行递归分解
             * */
            mergeSorting(array, mid + 1, right, temp);
            /*
             * 左右递归分解完成之后，已经到达栈顶，栈顶时，数组已经被分为每组只有一个元素的组
             * 然后从栈顶依次执行方法，非栈顶的方法等待栈顶方法执行完成
             * 合并分组开始执行，最先合并栈顶，栈顶的每组只有一个元素
             * 合并完成后，开始回溯
             * */
            merge(array, left, mid, right, temp);
        }
    }


    /**
     * 本次递归只对array[left]到array[right]之间的数进行合并
     *
     * @param array 用于排序的原始数组
     * @param left  左边有序序列的索引边界
     * @param mid   右边有序序列的前一个位置，即左边有序序列的最后一个位置
     * @param right 右边有序序列的索引边界
     * @param temp  用于中转的数组
     */
    private static void merge(int[] array, int left, int mid, int right, int[] temp) {

//        System.out.println("合并元素  左边界 = "+left+"\t右边界 = "+right);

        /*
         * 初始化leftScript，左边有序序列的初始索引
         * */
        int leftScript = left;
        /*
         * 初始化rightScript，右边有序序列的初始索引
         * */
        int rightScript = mid + 1;
        /*
         * 指向temp的当前索引
         * */
        int tempScript = 0;
        /*
         * 一、将左右两边有序的数据拼接
         *       按照规则填充到temp数组中
         *       直到左右两边的序列有一方处理完毕为止
         *     必须是 小于等于条件(<=) ，否则当mid == leftScript ，即到达栈顶，将元素分组到最后，每组只有2个元素时
         *          无法进入while (leftScript < mid && rightScript < right)循环，
         *          而左右两序列中较小的哪一个元素没有被填入temp数组
         *          导致在之后的将左右序列中，将剩余元素填充到temp，两边同时填充，合并分组之后是无序的，因此排序失败
         *
         * */
        while (leftScript <= mid && rightScript <= right) {
            /*
             * 将左边和右边相比较
             * */
            if (array[leftScript] <= array[rightScript]) {
                /*
                 *
                 * 较小的数是左边的数
                 * 把较小的数放入临时数组
                 * */
                temp[tempScript] = array[leftScript];
                leftScript++;
            } else {
                /*
                 * 较小的数是右边的数
                 * */
                temp[tempScript] = array[rightScript];
                rightScript++;
            }
            tempScript++;
        }
        /*
         * 二、把有剩余数组的一边（左边或者右边）的数据依次将剩余数据全部填充到temp中
         *
         *   2.把右边的剩余数据全部填充到temp中
         * */
        while (rightScript <= right) {
            temp[tempScript] = array[rightScript];
            tempScript++;
            rightScript++;
        }

        /*
         *
         * 把左边的剩余数据全部填充到temp中
         * */
        while (leftScript <= mid) {
            temp[tempScript] = array[leftScript];
            tempScript++;
            leftScript++;
        }

        /*
         * 三、将temp数组的元素拷贝到array中
         * */

        tempScript = 0;
        for (int i = left; i <= right; i++) {
            array[i] = temp[tempScript];
            tempScript++;
        }
    }
}
